package 热题100;

public class 热题4寻找两个正序数组的中位数 {
    public static void main(String[] args) {
        int[] arr1 = {1,2};
        int[] arr2 = {3,4};
        热题4寻找两个正序数组的中位数 o = new 热题4寻找两个正序数组的中位数();
        System.out.println(o.findMedianSortedArrays(arr1, arr2));
    }

    /**
     * 找除两个升序数组得中位数
     * 思路，常见一个数组长度为两个数组得长度和得一半，然后遍历两个数组，将较小得数添加到新得数组中
     * 最后根据两个数组得长度得奇偶性，奇数则返回结果数组得最后一个元素
     * 偶数则返回结果数组得倒数后两个数得平均数
     * @param nums1
     * @param nums2
     * @return
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int count = 0;
        int[] arr = new int[(len2 + len1) / 2 + 1];
        int oneIndex = 0;
        int twoIndex = 0;
        for(int i = 0 ;i < arr.length ;i ++){
            if(oneIndex < len1 && twoIndex < len2){
                if(nums1[oneIndex] >= nums2[twoIndex]){
                    arr[i] = nums2[twoIndex];
                    ++twoIndex;
                }else{
                    arr[i] = nums1[oneIndex];
                    ++oneIndex;
                }
            }else if(oneIndex >= len1){
                arr[i] = nums2[twoIndex];
                ++twoIndex;
            }else{
                arr[i] = nums1[oneIndex];
                ++oneIndex;
            }
        }

        if((len1 + len2) % 2 == 0){
            return (arr[arr.length - 2] + arr[arr.length - 1]) / 2.0;
        }else {
            return arr[arr.length - 1];
        }
    }
}
